/**
 * @file 015.字符串中的所有变位词.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-20
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        // s, p 一起哈希，滑窗 计数
        int m = s.length(), n = p.length();
        if (m < n) {
            return {};
        }
        vector<int> res;
        vector<int> cnt(26, 0); // map
        for (int i = 0; i < n; ++i) {
            --cnt[p[i] - 'a'];
            ++cnt[s[i] - 'a'];
        }
        if (isZeros(cnt)) { // O(26) -> O(1)
            res.push_back(0);
        }
        for (int i = n; i < m; ++i) {
            --cnt[s[i - n] - 'a']; // 左端口
            ++cnt[s[i] - 'a'];     // 右端口
            // print(cnt);
            if (isZeros(cnt)) {
                res.push_back(i - n + 1);
            }
        }
        return res;
    }

private:
    bool isZeros(vector<int> &nums)
    {
        for (int i = 0; i < 26; ++i) {
            if (nums[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    print(Solution().findAnagrams("cbaebabacd", "abc"));
    print(Solution().findAnagrams("baa", "aa"));

    return 0;
}